#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {};
    ListNode(int x): val(x), next(nullptr) {};
};

// 每次断开时需要把下一个节点记录下来
// 设置一个虚拟头节点
ListNode* swapPairs(ListNode* head) {
    ListNode* befordHead = new ListNode();
    befordHead->next = head;
    ListNode* current = befordHead;
    // 奇数个节点和偶数个节点
    while (current->next != nullptr && current->next->next != nullptr) {
        // ListNode* temp1 = current->next;
        // current->next = current->next->next; // 需要先记录他的下个（上一行）

        // ListNode* temp2 = temp1->next->next;
        // current->next->next = temp1; // 需要先记录他的下个（上一行）

        // current->next->next->next = temp2;
        // current = current->next->next;

        // 先记录临时节点
        ListNode* temp1 = current->next;
        ListNode* temp2 = temp1->next->next;

        current->next = current->next->next;
        current->next->next = temp1;
        current->next->next->next = temp2;

        current = current->next->next;
    }
    return befordHead->next;
}

void printListNode(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
}

int main() {
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(6);
    ListNode* node4 = new ListNode(3);
    ListNode* node5 = new ListNode(4);
    ListNode* node6 = new ListNode(5);
    ListNode* node7 = new ListNode(6);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = node7;

    cout << "origin: " << "\n";
    printListNode(node1);

    node1 = swapPairs(node1);

    cout << "after: " << "\n";
    printListNode(node1);

    return 0;
}